// https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
var inorderTraversal = function (root) {
    //递归法
    //return root ? [...inorderTraversal(root.left),root.val,...inorderTraversal(root.right)]:[];

    //迭代法 用数组模拟栈 先放左节点，后放右节点
    let list = [];
    let stack = [];
    if (!root) return [];
    while (root || stack.length) {
        // 3.1 栈添加左子树
        while (root) {
            stack.push(root);
            root = root.left;
        }

        // 3.2 推出
        root = stack.pop();
        list.push(root.val);

        root = root.right;
    }
    return list;
};